Дискретная математика: Сила рекуррентных соотношений

Рекуррентные соотношения служат глубоким математическим мостом между рекурсивными определениями и явными функциональными решениями, отражая суть Разделяй и властвуй стратегий. Определяя последовательности через самореференциальные шаги, мы моделируем всё — от комбинаторных структур, таких как числа Стирлинга и Каталана, до гипер-роста функции Аккермана.

1. Комбинаторное разнообразие

Истинная сила рекуррентных соотношений заключается в широте последовательностей, которые они охватывают. Например, числа второго рода числа Стирлинга определяются по формуле:

$$S_{n+1,k} = S_{n,k-1} + nS_{n,k}$$

Они подсчитывают количество способов разделить множество из $n+1$ элементов на $k$ непустых подмножеств. Аналогично, числа Каталана ($C_n$) описывают триангуляцию выпуклых многоугольников — деление выпуклого пятиугольника на треугольники с помощью непересекающихся диагоналей.

2. Моделирование структуры и беспорядки

Рекуррентные соотношения предоставляют строгую основу для неочевидных задач подсчёта, таких как беспорядки. Техническое название перестановки, в которой ни один элемент не находится на своём исходном месте, называется беспорядком ($D_n$).

Рекуррентное соотношение для беспорядков

Соотношение для беспорядков задаётся формулой:

$$D_n - nD_{n-1} = (-1)^n$$

Или альтернативно: $D_n = (n-1)(D_{n-1} + D_{n-2})$. Это подсчитывает, сколько способов существует, чтобы $n$ человек получили чужие шляпы на стойке для шляп.

3. Границы роста и сложности

Рекуррентные соотношения определяют как сверхэффективные, так и вычислительно "взрывные" процессы:

Подход «разделяй и властвуй»: Бинарный поиск моделируется как $a_n = c a_{n/m} + d$, что даёт логарифмическое время выполнения.
Функция Аккермана: Определяет рекурсивную глубину, которая растёт быстрее любой полиномиальной или экспоненциальной функции: $$AO(x + 3, y, z + 1) = AO(x + 2, y, AO(x + 3, y, z))$$

🎯 Технический обзор профессора

При работе с неоднородными соотношениями помните форму: $U_n = V_n + g(n)$, где $V_n$ — однородное решение. Для линейных однородных соотношений с постоянными коэффициентами, например $a_n = c_1 a_{n-1} + c_2 a_{n-2}$, найдите корни характеристического уравнения $t^2 - c_1 t - c_2 = 0$.

ВОПРОС 1

Что такое рекуррентное соотношение порядка $n$, линейное, однородное с постоянными коэффициентами?

Соотношение вида $a_n = c_1 a_{n-1} + c_2 a_{n-2} + \ldots + c_k a_{n-k}$, где $c_k \neq 0$ и все $c_i$ — константы.

Соотношение, при котором $a_n$ всегда является степенью $n$.

Соотношение, которое включает функцию $f(n)$, добавленную к линейным членам.

Уравнение, где коэффициенты меняются в зависимости от значения $n$.

ВОПРОС 2

Рассматривая последовательность $S_n$ из $n$-битовых строк, не содержащих '010', каково значение $S_4$?

ВОПРОС 3

Как работает бинарный поиск и какие свойства должен иметь входной массив?

Он проверяет каждый элемент последовательно; входной массив может быть в любом порядке.

Требуется отсортированный входной массив; он многократно делит интервал поиска пополам, чтобы найти ключ.

Он работает только с простыми числами; входные данные должны быть случайными.

Он использует характеристическое уравнение для прогнозирования индекса; входные данные должны быть числовыми.

ВОПРОС 4

В случае поиска ключа = 'G' в отсортированном списке от A до J (индексы 1–10), что происходит на первом шаге алгоритма 7.3.2?

Алгоритм сравнивает 'G' с 'E' (индекс 5) и переходит к верхней половине.

Алгоритм сравнивает 'G' с 'A' и увеличивает счётчик.

Алгоритм определяет 'G' как 7-ю букву и немедленно возвращает результат.

Алгоритм делит список на 4 стержня и перемещает 'G'.

ВОПРОС 5

Каково значение константы Аккермана AO(2, y, z)?

$y + z$

$z + 1$

yᶻ

Вызов: Алгоритмическое моделирование

Сортировка выбором и 4-стержневая головоломка Ханиоя

Рекуррентные соотношения позволяют нам точно рассчитывать стоимость рекурсивной логики. Рассмотрим сортировку выбором алгоритм и головоломку Ханиоя с четырьмя стержнями вариацию.

Вопрос 1

[Задание на написание] Напишите сортировку выбором на псевдокоде. (Требование по объёму: ~135 слов).

Псевдокод и анализ:

selection_sort(A, n) {
  если (n <= 1) вернуть;
  max_idx = 0;
  для i от 1 до n-1:
    если (A[i] > A[max_idx]) max_idx = i;
  поменять(A[max_idx], A[n-1]);
  selection_sort(A, n-1);
}

Этот алгоритм работает путём рекурсивного поиска максимального элемента в текущем диапазоне и помещения его в конец. Рекуррентное соотношение: $T(n) = T(n-1) + (n-1)$, где $(n-1)$ — количество сравнений в цикле. Решение методом итерации даёт $T(n) = (n-1) + (n-2) + \ldots + 1 = n(n-1)/2$, что составляет $\Theta(n^2)$. Такая квадратичная сложность делает его неэффективным для больших наборов данных по сравнению с методами типа «разделяй и властвуй».

Вопрос 2

Как алгоритм головоломки Ханиоя с четырьмя стержнями оптимизирует движение по сравнению со стандартной версией с тремя стержнями?

Решение: Алгоритм разбивает диски: фиксируем $k_n$ дисков внизу стержня 1. Перемещаем $n - k_n$ верхних дисков на стержень 2, используя все четыре стержня. Затем перемещаем $k_n$ нижних дисков со стержня 1 на стержень 4, применяя оптимальный трёхстержневой алгоритм. Наконец, перемещаем $n - k_n$ дисков со стержня 2 на стержень 4, снова используя четыре стержня. Такое разбиение значительно сокращает общее количество ходов по сравнению со стандартной сложностью $2^n - 1$.